{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Total Cost to Hire K Workers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers #simulation #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针 #模拟 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: totalCost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #雇佣 K 位工人的总代价"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>costs</code>&nbsp;，其中&nbsp;<code>costs[i]</code>&nbsp;是雇佣第 <code>i</code>&nbsp;位工人的代价。</p>\n",
    "\n",
    "<p>同时给你两个整数&nbsp;<code>k</code> 和&nbsp;<code>candidates</code>&nbsp;。我们想根据以下规则恰好雇佣&nbsp;<code>k</code>&nbsp;位工人：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>总共进行&nbsp;<code>k</code>&nbsp;轮雇佣，且每一轮恰好雇佣一位工人。</li>\n",
    "\t<li>在每一轮雇佣中，从最前面 <code>candidates</code>&nbsp;和最后面 <code>candidates</code>&nbsp;人中选出代价最小的一位工人，如果有多位代价相同且最小的工人，选择下标更小的一位工人。\n",
    "\t<ul>\n",
    "\t\t<li>比方说，<code>costs = [3,2,7,7,1,2]</code> 且&nbsp;<code>candidates = 2</code>&nbsp;，第一轮雇佣中，我们选择第&nbsp;<code>4</code>&nbsp;位工人，因为他的代价最小&nbsp;<code>[<em>3,2</em>,7,7,<em><strong>1</strong>,2</em>]</code>&nbsp;。</li>\n",
    "\t\t<li>第二轮雇佣，我们选择第&nbsp;<code>1</code>&nbsp;位工人，因为他们的代价与第&nbsp;<code>4</code>&nbsp;位工人一样都是最小代价，而且下标更小，<code>[<em>3,<strong>2</strong></em>,7,<em>7,2</em>]</code>&nbsp;。注意每一轮雇佣后，剩余工人的下标可能会发生变化。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "\t<li>如果剩余员工数目不足 <code>candidates</code>&nbsp;人，那么下一轮雇佣他们中代价最小的一人，如果有多位代价相同且最小的工人，选择下标更小的一位工人。</li>\n",
    "\t<li>一位工人只能被选择一次。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回雇佣恰好<em>&nbsp;</em><code>k</code>&nbsp;位工人的总代价。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>costs = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 4\n",
    "<b>输出：</b>11\n",
    "<b>解释：</b>我们总共雇佣 3 位工人。总代价一开始为 0 。\n",
    "- 第一轮雇佣，我们从 [<strong><em>17,12,10,2</em></strong>,7,<strong><em>2,11,20,8</em></strong>] 中选择。最小代价是 2 ，有两位工人，我们选择下标更小的一位工人，即第 3 位工人。总代价是 0 + 2 = 2 。\n",
    "- 第二轮雇佣，我们从 [<strong><em>17,12,10,7</em></strong>,<strong><em>2,11,20,8</em></strong>] 中选择。最小代价是 2 ，下标为 4 ，总代价是 2 + 2 = 4 。\n",
    "- 第三轮雇佣，我们从 [<strong><em>17,12,10,7,11,20,8</em></strong>] 中选择，最小代价是 7 ，下标为 3 ，总代价是 4 + 7 = 11 。注意下标为 3 的工人同时在最前面和最后面 4 位工人中。\n",
    "总雇佣代价是 11 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>costs = [1,2,4,1], k = 3, candidates = 3\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>我们总共雇佣 3 位工人。总代价一开始为 0 。\n",
    "- 第一轮雇佣，我们从 [<strong><em>1,2,4,1</em></strong>] 中选择。最小代价为 1 ，有两位工人，我们选择下标更小的一位工人，即第 0 位工人，总代价是 0 + 1 = 1 。注意，下标为 1 和 2 的工人同时在最前面和最后面 3 位工人中。\n",
    "- 第二轮雇佣，我们从 [<strong><em>2,4,1</em></strong>] 中选择。最小代价为 1 ，下标为 2 ，总代价是 1 + 1 = 2 。\n",
    "- 第三轮雇佣，少于 3 位工人，我们从剩余工人 [<strong><em>2,4</em></strong>] 中选择。最小代价是 2 ，下标为 0 。总代价为 2 + 2 = 4 。\n",
    "总雇佣代价是 4 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= costs.length &lt;= 10<sup>5 </sup></code></li>\n",
    "\t<li><code>1 &lt;= costs[i] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= k, candidates &lt;= costs.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [total-cost-to-hire-k-workers](https://leetcode.cn/problems/total-cost-to-hire-k-workers/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [total-cost-to-hire-k-workers](https://leetcode.cn/problems/total-cost-to-hire-k-workers/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[17,12,10,2,7,2,11,20,8]\\n3\\n4', '[1,2,4,1]\\n3\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        n = len(costs)\n",
    "        min_costs = 0\n",
    "\n",
    "        if candidates * 2 < n:\n",
    "            pre = costs[:candidates]\n",
    "            suf = costs[-candidates:]\n",
    "            heapify(pre)\n",
    "            heapify(suf)\n",
    "            left, right = candidates, n - candidates - 1\n",
    "            while k > 0 and left <= right:\n",
    "                if pre[0] <= suf[0]:\n",
    "                    min_costs += heapreplace(pre, costs[left])\n",
    "                    left += 1\n",
    "                else:\n",
    "                    min_costs += heapreplace(suf, costs[right])\n",
    "                    right -= 1\n",
    "                k -= 1\n",
    "            if k == 0:\n",
    "                return min_costs\n",
    "            costs = pre + suf\n",
    "\n",
    "        costs.sort()\n",
    "        return min_costs + sum(costs[:k])\n",
    "        \n",
    "         \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        ans = 0\n",
    "        n = len(costs)\n",
    "\n",
    "        # if head slice and tail slice are not overlapped\n",
    "        if candidates * 2 < n:\n",
    "            prefix = costs[:candidates]\n",
    "            heapify(prefix)\n",
    "            suffix = costs[-candidates:]\n",
    "            heapify(suffix)\n",
    "\n",
    "            # 双指针：对撞，相遇时即为前k树之和\n",
    "            i, j = candidates, n - 1 - candidates\n",
    "            while k and i <= j:\n",
    "                if prefix[0] <= suffix[0]:\n",
    "                    ans += heapreplace(prefix, costs[i])\n",
    "                    i += 1\n",
    "                else:\n",
    "                    ans += heapreplace(suffix, costs[j])\n",
    "                    j -= 1\n",
    "                k -= 1\n",
    "            else:\n",
    "                costs = prefix + suffix\n",
    "                costs.sort()\n",
    "        else:\n",
    "            costs.sort()\n",
    "        return ans + sum(costs[:k])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        n = len(costs)\n",
    "        ans = 0\n",
    "        if 2*candidates >= n:\n",
    "            heapq.heapify(costs)\n",
    "            for _ in range(k):\n",
    "                ans += heapq.heappop(costs)\n",
    "        else:\n",
    "            Lcost , Rcost = costs[:candidates], costs[-candidates:]\n",
    "            Lindex, Rindex = candidates-1, n-candidates\n",
    "            heapq.heapify(Lcost)\n",
    "            heapq.heapify(Rcost)\n",
    "            for _ in range(k):\n",
    "                if Lindex == Rindex:\n",
    "                    if not Lcost:\n",
    "                        ans += heapq.heappop(Rcost)\n",
    "                    elif not Rcost:\n",
    "                        ans += heapq.heappop(Lcost)\n",
    "                    elif Lcost[0] <= Rcost[0]:\n",
    "                        ans += heapq.heappop(Lcost)\n",
    "                    else:\n",
    "                        ans += heapq.heappop(Rcost)\n",
    "                else:\n",
    "                    if Lcost[0] <= Rcost[0]:\n",
    "                        ans += heapq.heappop(Lcost)\n",
    "                        Lindex += 1\n",
    "                        if Rindex != Lindex:\n",
    "                            heapq.heappush(Lcost,costs[Lindex])\n",
    "                    else:\n",
    "                        ans += heapq.heappop(Rcost)\n",
    "                        Rindex -= 1\n",
    "                        if Rindex != Lindex:\n",
    "                            heapq.heappush(Rcost,costs[Rindex])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        n = len(costs)\n",
    "        ans = 0\n",
    "        if candidates * 2 < n:\n",
    "            pre = costs[:candidates]\n",
    "            heapq.heapify(pre)\n",
    "            end = costs[-candidates:]\n",
    "            heapq.heapify(end)\n",
    "            i = candidates\n",
    "            j = n - candidates - 1\n",
    "            while k > 0 and i <= j:\n",
    "                if pre[0] <= end[0]:\n",
    "                    ans += heapq.heapreplace(pre, costs[i])\n",
    "                    i += 1\n",
    "                else:\n",
    "                    ans += heapq.heapreplace(end, costs[j])\n",
    "                    j -= 1\n",
    "                k -= 1\n",
    "            costs = pre + end\n",
    "        costs.sort()\n",
    "        return ans + sum(costs[:k])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        ans  = 0\n",
    "        n = len(costs)\n",
    "        if candidates*2<n:  # 没有重叠\n",
    "            pre = costs[:candidates]\n",
    "            heapify(pre)\n",
    "\n",
    "            post = costs[-candidates:]\n",
    "            heapify(post)\n",
    "            # i,j分别代表前candidates个元素中最后一个元素的下标，后candiates个元素中第一个元素的下标\n",
    "            i, j = candidates, n-1-candidates\n",
    "            # 在pre区间和post区间重叠之前，需要一直更新堆，重叠之后，就直接堆剩余的所有元素进行操作就可以了\n",
    "            # 当然，如果在此之前，员工数量k耗尽，则循环结束\n",
    "            while k and i<=j:\n",
    "                if pre[0]<= post[0]:   # 堆顶元素比较，取小的那个堆顶元素，如果相等，则取前面那个堆的堆顶元素\n",
    "                    ans+= heapreplace(pre, costs[i])  # 堆顶元素出堆，并让cost[i]入堆，一直保持堆内的元素数量为candiates个\n",
    "                    i +=1\n",
    "                else:\n",
    "                    ans += heapreplace(post, costs[j])\n",
    "                    j -=1\n",
    "                k-=1\n",
    "            # 如果k还没有耗尽，此时i和j已经连接到一起了\n",
    "            # 两个堆化（heapify）之后的元素直接相加并不会保持堆的性质，costs此时只是一个包含原先两个堆中所有元素的list\n",
    "            costs = pre+post  \n",
    "        costs.sort() # 将这个list排序，并取前面的k个元素来补充答案\n",
    "        return ans + sum(costs[:k])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq \n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs, k: int, candidates: int) -> int:\n",
    "        i_left = candidates - 1\n",
    "        i_right = len(costs) - candidates\n",
    "        total_cost = 0\n",
    "\n",
    "        if i_left < i_right-1:\n",
    "            flag = False\n",
    "            cands1 = costs[: i_left+1]\n",
    "            cands2 = costs[i_right: ]\n",
    "            heapq.heapify(cands1)\n",
    "            heapq.heapify(cands2)\n",
    "        else:\n",
    "            cands = costs\n",
    "            heapq.heapify(cands)\n",
    "        \n",
    "        for i in range(k):\n",
    "            if i_left < i_right-1:\n",
    "                c1_min = heapq.heappop(cands1)\n",
    "                c2_min = heapq.heappop(cands2)\n",
    "                if c1_min <= c2_min:\n",
    "                    i_left += 1\n",
    "                    heapq.heappush(cands2, c2_min)\n",
    "                    heapq.heappush(cands1, costs[i_left])\n",
    "                else:\n",
    "                    i_right -= 1\n",
    "                    heapq.heappush(cands1, c1_min)\n",
    "                    heapq.heappush(cands2, costs[i_right])\n",
    "                total_cost += min(c1_min, c2_min)\n",
    "                if i_left >= i_right-1:\n",
    "                    cands = cands1 + cands2\n",
    "                    heapq.heapify(cands)\n",
    "            else:\n",
    "                c_min = heapq.heappop(cands)\n",
    "                total_cost += c_min                \n",
    "        return total_cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        if candidates*2+k-1>=len(costs):\n",
    "            return sum(sorted(costs)[:k])\n",
    "        H = []\n",
    "        heapq.heapify(H)\n",
    "        l, r = 0, len(costs)-1\n",
    "        ans = count = 0\n",
    "        for i in range(candidates):\n",
    "            heapq.heappush(H, (costs[l], l))\n",
    "            l += 1\n",
    "        for i in range(candidates):\n",
    "            heapq.heappush(H, (costs[r], r))\n",
    "            r -= 1\n",
    "        while count < k:\n",
    "            cost, pos = heapq.heappop(H)\n",
    "            ans += cost\n",
    "            if l <= r:\n",
    "                if pos <= l:\n",
    "                    heapq.heappush(H, (costs[l], l))\n",
    "                    l += 1\n",
    "                elif pos >= r:\n",
    "                    heapq.heappush(H, (costs[r], r))\n",
    "                    r -= 1\n",
    "            count += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        n = len(costs)\n",
    "        min_costs = 0\n",
    "\n",
    "        if candidates * 2 < n:\n",
    "            pre = costs[:candidates]\n",
    "            suf = costs[-candidates:]\n",
    "            heapify(pre)\n",
    "            heapify(suf)\n",
    "            left, right = candidates, n - candidates - 1\n",
    "            while k > 0 and left <= right:\n",
    "                if pre[0] <= suf[0]:\n",
    "                    min_costs += heapreplace(pre, costs[left])\n",
    "                    left += 1\n",
    "                else:\n",
    "                    min_costs += heapreplace(suf, costs[right])\n",
    "                    right -= 1\n",
    "                k -= 1\n",
    "            costs = pre + suf\n",
    "\n",
    "        if k > 0:\n",
    "            print(costs, min_costs)\n",
    "            costs.sort()\n",
    "            return min_costs + sum(costs[:k])\n",
    "        \n",
    "        return min_costs\n",
    "         \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        \"\"\"\n",
    "        key intuition: if the number of workers <= 2 * candidates, it means we can choose from all the workers, so we would just need to choose the smallest k workers \n",
    "        \"\"\"\n",
    "        num_workers = len(costs)\n",
    "        total_cost = 0 \n",
    "        # if the 2 * candidates < number of workers: \n",
    "        if 2 * candidates < num_workers:\n",
    "            # construct two min heaps, one for the first candidates workers, and second for the last candidates workers \n",
    "            first_heap = costs[:candidates]\n",
    "            heapq.heapify(first_heap)\n",
    "            last_heap = costs[-candidates:]\n",
    "            heapq.heapify(last_heap)\n",
    "            # use two pointers, one point to the next candidate to add to the first candidates, and the second to point to the next candidates to add to the last candidates \n",
    "            first_idx = candidates\n",
    "            last_idx = num_workers - candidates - 1\n",
    "            # while we still need to hire and the two pointers don't overlap\n",
    "            print(\"first_idx: \", first_idx)\n",
    "            print(\"last_idx: \", last_idx)\n",
    "            while k and first_idx <= last_idx:\n",
    "                # if the min in first candidates <= min in last candidates \n",
    "                if first_heap[0] <= last_heap[0]:\n",
    "                    # replace the min heap for first candidates \n",
    "                    total_cost += heapq.heapreplace(first_heap, costs[first_idx])\n",
    "                    first_idx += 1\n",
    "                else: \n",
    "                    # replace the min heap for the last candidates \n",
    "                    total_cost += heapq.heapreplace(last_heap, costs[last_idx])\n",
    "                    last_idx -= 1\n",
    "                k -= 1\n",
    "                print(\"total cost: \", total_cost)\n",
    "            # concatinate two min heaps and sort \n",
    "            costs = first_heap + last_heap\n",
    "        # hire the remaining candidates from the combined list \n",
    "        # return the total cost\n",
    "        costs = sorted(costs)\n",
    "        return total_cost + sum(costs[:k])\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        n = len(costs)\n",
    "        left_heap = []\n",
    "        right_heap = []\n",
    "        left, right = 0, n-1\n",
    "        cnt = 0\n",
    "        for i in range(candidates):\n",
    "            j = n-i-1\n",
    "            if(i < j):\n",
    "                heapq.heappush(left_heap, costs[i])\n",
    "                heapq.heappush(right_heap, costs[j])\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            elif(i == j):\n",
    "                heapq.heappush(left_heap, costs[i])\n",
    "                left += 1\n",
    "            else:\n",
    "                break\n",
    "        result = 0\n",
    "        for _ in range(k):\n",
    "            v1 = left_heap[0] if left_heap else float('inf')\n",
    "            v2 = right_heap[0] if right_heap else float('inf')\n",
    "            if(v1 <= v2):\n",
    "                result += v1 \n",
    "                heapq.heappop(left_heap)\n",
    "                if(left <= right):\n",
    "                    heapq.heappush(left_heap, costs[left])\n",
    "                    left += 1\n",
    "            else:\n",
    "                result += v2 \n",
    "                heapq.heappop(right_heap)\n",
    "                if(left <= right):\n",
    "                    heapq.heappush(right_heap, costs[right])\n",
    "                    right -= 1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        res = 0\n",
    "        temp = costs\n",
    "        if candidates * 2 < len(costs):\n",
    "            left = costs[:candidates]\n",
    "            heapify(left)\n",
    "            right = costs[-candidates:]\n",
    "            heapify(right)\n",
    "            l,r = candidates,len(costs)-1-candidates\n",
    "            while k > 0 and l<=r:\n",
    "                if left[0] <= right[0]:\n",
    "                    res+=heapreplace(left,costs[l])\n",
    "                    l+=1\n",
    "                else:\n",
    "                    res+=heapreplace(right,costs[r])\n",
    "                    r-=1\n",
    "                k-=1\n",
    "            temp = left + right\n",
    "        temp = sorted(temp)\n",
    "        return res+sum(temp[:k])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        n = len(costs)\n",
    "        if k >= n:\n",
    "            return sum(costs)\n",
    "        ans = 0\n",
    "        if candidates*2>=n:\n",
    "            return sum(sorted(costs)[:k])\n",
    "        pre = costs[:candidates]\n",
    "        heapify(pre)\n",
    "        suff = costs[-candidates:]\n",
    "        heapify(suff)\n",
    "        l = candidates\n",
    "        r = n-1-candidates\n",
    "        while k:\n",
    "            if not pre:\n",
    "                for _ in range(k):\n",
    "                    ans += heappop(suff)\n",
    "                return ans\n",
    "            if not suff:\n",
    "                for _ in range(k):\n",
    "                    ans += heappop(pre)\n",
    "                return ans\n",
    "            if pre[0]<=suff[0]:\n",
    "                ans += heappop(pre)\n",
    "                if l <= r:\n",
    "                    heappush(pre,costs[l])\n",
    "                    l += 1\n",
    "            else:\n",
    "                ans += heappop(suff)\n",
    "                if l <= r:\n",
    "                    heappush(suff,costs[r])\n",
    "                    r -= 1\n",
    "            k -= 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        n = len(costs) \n",
    "        l, r = candidates-1, n-candidates \n",
    "        Q = []\n",
    "        ans = 0\n",
    "        \n",
    "        if l < r:\n",
    "            for i in range(l+1):\n",
    "                heapq.heappush(Q, (costs[i], i)) \n",
    "            for i in range(r,n):\n",
    "                heapq.heappush(Q, (costs[i], i))\n",
    "            while k > 0 and l < r:\n",
    "                x, i = heapq.heappop(Q) \n",
    "                ans += x \n",
    "                if i <= l:\n",
    "                    l += 1\n",
    "                    if l < r:\n",
    "                        heapq.heappush(Q, (costs[l], l))\n",
    "                elif i >= r:\n",
    "                    r -= 1 \n",
    "                    if l < r:\n",
    "                        heapq.heappush(Q, (costs[r], r))\n",
    "                k -= 1\n",
    "\n",
    "            while k > 0:\n",
    "                x, _ = heapq.heappop(Q)\n",
    "                ans += x \n",
    "                k-=1 \n",
    "        else:\n",
    "            costs.sort() \n",
    "            ans = sum(costs[:k])\n",
    "        return ans \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        head = costs[:candidates]\n",
    "        heapify(head)\n",
    "        costs = costs[candidates:]\n",
    "        tail = costs[-candidates:]\n",
    "        heapify(tail)\n",
    "        costs = costs[:-candidates]\n",
    "        costs = deque(costs)\n",
    "        res = 0\n",
    "        for _ in range(k):\n",
    "            if head and tail:\n",
    "                if head[0] <= tail[0]:\n",
    "                    res += heappop(head)\n",
    "                    if costs:\n",
    "                        heappush(head, costs.popleft())\n",
    "                else:\n",
    "                    res += heappop(tail)\n",
    "                    if costs:\n",
    "                        heappush(tail, costs.pop())\n",
    "            else:\n",
    "                if head:\n",
    "                    res += heappop(head)\n",
    "                else:\n",
    "                    res += heappop(tail)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        costs_len = len(costs)\n",
    "\n",
    "        if costs_len<= 2*candidates:\n",
    "            data_list = sorted(costs)\n",
    "            return sum(data_list[:k])\n",
    "        heap = []\n",
    "        for i in range(candidates):\n",
    "            heappush(heap, (costs[i], i))\n",
    "        for i in range(costs_len-1, costs_len-candidates-1, -1):\n",
    "            heappush(heap, (costs[i], i))\n",
    "        left = candidates\n",
    "        right = costs_len-1-candidates\n",
    "        # print(left,right,heap)\n",
    "        ans = []\n",
    "        while left<= right and len(ans)<k:\n",
    "            cost, index = heappop(heap)\n",
    "            ans.append(cost)\n",
    "            if index < left:\n",
    "                heappush(heap, (costs[left], left))\n",
    "                left+=1\n",
    "            else:\n",
    "                heappush(heap, (costs[right], right))\n",
    "                right-=1\n",
    "        ans_len = len(ans)\n",
    "        # print(ans)\n",
    "        if (t:=k-ans_len)>0:\n",
    "            for i in range(t):\n",
    "                ans.append(heappop(heap)[0])\n",
    "        # print(ans)\n",
    "        return sum(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        n = len(costs)\n",
    "        if n <= 2 * candidates:\n",
    "            costs.sort()\n",
    "            return sum(costs[:k])\n",
    "        pq = []\n",
    "        left, right = 0, n-1\n",
    "        for _ in range(candidates):\n",
    "            heappush(pq, (costs[left], left))\n",
    "            heappush(pq, (costs[right], right))\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        ans = 0\n",
    "        while k > 0:\n",
    "            c, i = heappop(pq)\n",
    "            ans += c\n",
    "            k -= 1\n",
    "            if i < left:\n",
    "                heappush(pq, (costs[left], left))\n",
    "                left += 1\n",
    "            else:\n",
    "                heappush(pq, (costs[right], right))\n",
    "                right -= 1\n",
    "            if left > right:\n",
    "                for _ in range(k):\n",
    "                    c, x = heappop(pq)\n",
    "                    ans += c\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        if len(costs) <= candidates*2:\n",
    "            costs.sort()\n",
    "            return sum(costs[:k])\n",
    "        N = len(costs)\n",
    "        h = [(n, i) for i, n in enumerate(costs[:candidates])]\n",
    "        h.extend((costs[i], N + i) for i in range(-candidates, 0))\n",
    "        heapify(h)\n",
    "        l, r = candidates, N - candidates - 1\n",
    "        res = 0\n",
    "        for _ in range(k):\n",
    "            n, off = heappop(h)\n",
    "            res += n\n",
    "            if r >= l:\n",
    "                if off < l:\n",
    "                    heappush(h, (costs[l], l))\n",
    "                    l += 1\n",
    "                else:\n",
    "                    heappush(h, (costs[r], r))\n",
    "                    r -= 1\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        n = len(costs)\n",
    "        # if candidates > n//2:  # [0,1,2,3, 4]\n",
    "        if candidates * 2 >= n:\n",
    "            return sum(sorted(costs)[: k])\n",
    "        heap = []\n",
    "        i, j = 0, n -1\n",
    "        for _ in range(candidates):\n",
    "            heapq.heappush(heap, [costs[i], i, 0]) # left\n",
    "            i += 1\n",
    "            heapq.heappush(heap, [costs[j], j, 1]) # right\n",
    "            j -= 1\n",
    "        i -= 1\n",
    "        j += 1\n",
    "        res = 0\n",
    "        for _ in range(k):\n",
    "            num, index, d = heapq.heappop(heap)\n",
    "            res += num\n",
    "            if d == 0:\n",
    "                i += 1\n",
    "                if i < j: # this line!!!!!!\n",
    "                    heapq.heappush(heap, [costs[i], i, 0])\n",
    "            else:\n",
    "                j -= 1\n",
    "                if i < j: # this line !!!!\n",
    "                    heapq.heappush(heap, [costs[j], j, 1])\n",
    "        return res\n",
    "  \n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        if candidates * 2 >= len(costs):\n",
    "            return sum(sorted(costs)[:k])\n",
    "\n",
    "        leftHeap = []\n",
    "        rightHeap = []\n",
    "        for i in range(candidates):\n",
    "            heapq.heappush(leftHeap, (costs[i], i))\n",
    "            heapq.heappush(rightHeap, (costs[len(costs) - i - 1], len(costs) - i - 1))\n",
    "        heapq.heappush(leftHeap, (100001, 100001))\n",
    "        heapq.heappush(rightHeap, (100001, 100001))\n",
    "        leftFill = candidates\n",
    "        rightFill = len(costs) - 1 - candidates\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(k):\n",
    "            if leftHeap[0][0] <= rightHeap[0][0]:\n",
    "                ans += heapq.heappop(leftHeap)[0]\n",
    "                if leftFill <= rightFill:\n",
    "                    heapq.heappush(leftHeap, (costs[leftFill], leftFill))\n",
    "                    leftFill += 1\n",
    "            else:\n",
    "                ans += heapq.heappop(rightHeap)[0]\n",
    "                if leftFill <= rightFill:\n",
    "                    heapq.heappush(rightHeap, (costs[rightFill], rightFill))\n",
    "                    rightFill -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        if 2 * candidates >= len(costs):\n",
    "            h = [-costs[i] for i in range(k)]\n",
    "            heapq.heapify(h)\n",
    "            for i in range(k, len(costs)):\n",
    "                if -costs[i] > h[0]:\n",
    "                    heapq.heappop(h)\n",
    "                    heapq.heappush(h, -costs[i])\n",
    "            return -sum(h)\n",
    "        else:\n",
    "            front_h = [(costs[i], i) for i in range(candidates)]\n",
    "            back_h = [(costs[len(costs)-1-i], len(costs)-1-i) for i in range(candidates)]\n",
    "            heapq.heapify(front_h)\n",
    "            heapq.heapify(back_h)\n",
    "            i, j = candidates, len(costs)-candidates-1\n",
    "            ans = 0\n",
    "            count = 0\n",
    "            while i <= j and count < k:\n",
    "                count += 1\n",
    "                if front_h[0][0] <= back_h[0][0]:\n",
    "                    val, idx = heapq.heappop(front_h)\n",
    "                    ans += val\n",
    "                    heapq.heappush(front_h, (costs[i], i))\n",
    "                    i += 1\n",
    "                elif front_h[0][0] > back_h[0][0]:\n",
    "                    val, idx = heapq.heappop(back_h)\n",
    "                    ans += val\n",
    "                    heapq.heappush(back_h, (costs[j], j))\n",
    "                    j -= 1\n",
    "            while back_h:\n",
    "                val, idx = back_h.pop()\n",
    "                heapq.heappush(front_h, (val, idx))\n",
    "            for _ in range(k-count):\n",
    "                val, idx = heapq.heappop(front_h)\n",
    "                ans += val \n",
    "            return ans\n",
    "\n",
    "                    \n",
    "                    \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        deq, n = [], len(costs)\n",
    "        j = n - 1\n",
    "        for i in range(candidates):\n",
    "            heappush(deq, [costs[i], 0])\n",
    "            if j <= i + 1: \n",
    "                i += 1\n",
    "                break\n",
    "            heappush(deq, [costs[j], 1])\n",
    "            j -= 1\n",
    "        else:\n",
    "            i = candidates\n",
    "        res = 0\n",
    "        for _ in range(k):\n",
    "            v, p = heappop(deq)\n",
    "            res += v\n",
    "            if i <= j:\n",
    "                if p:\n",
    "                    heappush(deq, [costs[j], 1])\n",
    "                    j -= 1\n",
    "                else:\n",
    "                    heappush(deq, [costs[i], 0])\n",
    "                    i += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        heap = []\n",
    "        que = deque()\n",
    "        if 2 * candidates >= len(costs):\n",
    "            heap = [(cost, 0) for cost in costs[:candidates]] + [(cost, 1) for cost in costs[candidates:]]\n",
    "            que = deque([])\n",
    "        else:\n",
    "            heap = [(cost, 0,) for cost in costs[:candidates]] + [(cost, 1) for cost in costs[len(costs) - candidates:]]\n",
    "            que = deque([costs[i] for i in range(candidates, len(costs) - candidates)])\n",
    "        # print(heap, que)\n",
    "        heapq.heapify(heap)\n",
    "        # print(heap, que)\n",
    "        total_cost = 0\n",
    "        for _ in range(k):\n",
    "            cost, index = heapq.heappop(heap)\n",
    "\n",
    "            total_cost += cost\n",
    "            if index == 0:\n",
    "                if que:\n",
    "                    heapq.heappush(heap, (que.popleft(), 0))\n",
    "            else:\n",
    "                if que:\n",
    "                    heapq.heappush(heap, (que.pop(), 1))\n",
    "            # print(cost, index, heap)\n",
    "        return total_cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        res = 0\n",
    "        pnum = 0\n",
    "        h = []\n",
    "        heapify(h)\n",
    "        left = 0\n",
    "        right = len(costs)-1\n",
    "        while left<right and candidates>0:\n",
    "            heappush(h,[costs[left],0])\n",
    "            heappush(h,[costs[right],1])\n",
    "            left+=1\n",
    "            right-=1\n",
    "            candidates-=1\n",
    "        \n",
    "        if candidates>0 and left==right:\n",
    "            heappush(h,[costs[right],1])\n",
    "            right-=1\n",
    "        \n",
    "        while k>0:\n",
    "            tmp = heappop(h)\n",
    "            res += tmp[0]\n",
    "            if right>=left:\n",
    "                if tmp[1]==0:\n",
    "                    heappush(h,[costs[left],0])\n",
    "                    left+=1\n",
    "                else:\n",
    "                    heappush(h,[costs[right],1])\n",
    "                    right-=1\n",
    "            k-=1\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        n = len(costs)\n",
    "        ans = 0\n",
    "        left = 0\n",
    "        right = n - 1\n",
    "        minHeap = []\n",
    "        cc = candidates*2\n",
    "        while left <= right and cc > 0:\n",
    "            if (left <= right):\n",
    "                heapq.heappush(minHeap,[costs[left],-1]) # -1表示来自于左边\n",
    "                left += 1\n",
    "                cc -= 1\n",
    "            if (left <= right):\n",
    "                heapq.heappush(minHeap,[costs[right],1]) # 1表示来自于右边\n",
    "                right -= 1\n",
    "                cc -= 1\n",
    "\n",
    "        cnts = 0\n",
    "        while cnts != k:\n",
    "            val,mark = heapq.heappop(minHeap)\n",
    "            # print(val,mark,minHeap)\n",
    "            if mark == -1:\n",
    "                if left <= right:\n",
    "                    heapq.heappush(minHeap,[costs[left],-1])\n",
    "                    left += 1\n",
    "            elif mark == 1:\n",
    "                if left <= right:\n",
    "                    heapq.heappush(minHeap,[costs[right],1])\n",
    "                    right -= 1\n",
    "            ans += val \n",
    "            cnts += 1\n",
    "        return ans \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        dq = deque(costs)\n",
    "        q = []\n",
    "        for i in range(candidates):\n",
    "            if dq:\n",
    "                heappush(q, [dq.popleft(), 0])\n",
    "        for i in range(candidates):\n",
    "            if dq:\n",
    "                heappush(q, [dq.pop(), 1])\n",
    "        res = 0\n",
    "        for _ in range(k):\n",
    "            c, flag = heappop(q)\n",
    "            res += c\n",
    "            if flag == 0:\n",
    "                if dq: heappush(q,[dq.popleft(), 0])\n",
    "            else:\n",
    "                if dq:heappush(q, [dq.pop(), 1])\n",
    "        \n",
    "        return res\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        \n",
    "\n",
    "        from sortedcontainers import SortedList\n",
    "\n",
    "        s_list_1 = SortedList()\n",
    "        s_list_2 = SortedList()\n",
    "        \n",
    "        if len(costs)<candidates*2 + k:\n",
    "            return sum(sorted(costs)[:k])\n",
    "        \n",
    "        min_list = []\n",
    "        \n",
    "        for i in range(candidates,len(costs) - candidates):\n",
    "            min_list.append((costs[i],i))\n",
    "            \n",
    "        for i in range(candidates):\n",
    "            s_list_1.add((costs[i],i))\n",
    "        for i in range(len(costs)-1,len(costs) - candidates-1,-1):\n",
    "            s_list_2.add((costs[i],i))\n",
    "            \n",
    "        res = 0\n",
    "        for i in range(k):\n",
    "            #print(min_list)\n",
    "            if s_list_1[0]<s_list_2[0]:\n",
    "            \n",
    "                res += s_list_1[0][0]\n",
    "                del s_list_1[0]\n",
    "                \n",
    "                s_list_1.add(min_list[0])\n",
    "                del min_list[0]\n",
    "                \n",
    "                \n",
    "            else:\n",
    "                #print(s_list_2[0][0])\n",
    "                res += s_list_2[0][0]\n",
    "                del s_list_2[0]\n",
    "                s_list_2.add(min_list[-1])\n",
    "                del min_list[-1]\n",
    "    \n",
    "        return res\n",
    "                \n",
    "                \n",
    "            \n",
    "            \n",
    "        \n",
    "            \n",
    "            \n",
    "                \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        \n",
    "\n",
    "        from sortedcontainers import SortedList\n",
    "\n",
    "        s_list_1 = SortedList()\n",
    "        s_list_2 = SortedList()\n",
    "        \n",
    "        if len(costs)<candidates*2 + k:\n",
    "            return sum(sorted(costs)[:k])\n",
    "        \n",
    "        min_list = []\n",
    "        \n",
    "        for i in range(candidates,len(costs) - candidates):\n",
    "            min_list.append((costs[i],i))\n",
    "            \n",
    "        for i in range(candidates):\n",
    "            s_list_1.add((costs[i],i))\n",
    "        for i in range(len(costs)-1,len(costs) - candidates-1,-1):\n",
    "            s_list_2.add((costs[i],i))\n",
    "            \n",
    "        res = 0\n",
    "        for i in range(k):\n",
    "            #print(min_list)\n",
    "            if s_list_1[0]<s_list_2[0]:\n",
    "            \n",
    "                res += s_list_1[0][0]\n",
    "                del s_list_1[0]\n",
    "                \n",
    "                s_list_1.add(min_list[0])\n",
    "                del min_list[0]\n",
    "                \n",
    "                \n",
    "            else:\n",
    "                #print(s_list_2[0][0])\n",
    "                res += s_list_2[0][0]\n",
    "                del s_list_2[0]\n",
    "                s_list_2.add(min_list[-1])\n",
    "                del min_list[-1]\n",
    "    \n",
    "        return res\n",
    "                \n",
    "                \n",
    "            \n",
    "            \n",
    "        \n",
    "            \n",
    "            \n",
    "                \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        n = len(costs)\n",
    "        if 2*candidates>=n:\n",
    "            return sum(heapq.nsmallest(k,costs))\n",
    "        i, j = candidates, n - 1 - candidates\n",
    "        heap1 = costs[0:candidates]\n",
    "        heap2 = costs[-candidates:]\n",
    "        heapq.heapify(heap1)\n",
    "        heapq.heapify(heap2)\n",
    "        sumcost = 0\n",
    "        while k and i<=j:\n",
    "            if heap1[0]<=heap2[0]:\n",
    "                sumcost+=heap1[0]\n",
    "                heapq.heapreplace(heap1, costs[i])\n",
    "                i+=1\n",
    "            else:\n",
    "                sumcost+=heap2[0]\n",
    "                heapreplace(heap2,costs[j])\n",
    "                j-=1\n",
    "            k-=1\n",
    "        newcosts = heap1+heap2\n",
    "        newcosts.sort()\n",
    "        return sumcost+sum(newcosts[:k])\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        result, n = 0, len(costs)\n",
    "        if candidates * 2 >= n:\n",
    "            return sum(nsmallest(k, costs))\n",
    "        left, right = costs[:candidates], costs[-candidates:]\n",
    "        heapify(left) or heapify(right)\n",
    "        i, j = candidates-1, n-candidates\n",
    "        while k and i+1 < j:\n",
    "            if left[0] <= right[0]:\n",
    "                result += heapreplace(left, costs[i := i+1])\n",
    "            else:\n",
    "                result += heapreplace(right, costs[j := j-1])\n",
    "            k -= 1\n",
    "        if k:\n",
    "            result += sum(nsmallest(k, heapq.merge(left, right)))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        \n",
    "        def cmp(a: int, b: int) -> int:\n",
    "            if costs[a] == costs[b]:\n",
    "                return a - b\n",
    "            return costs[a] - costs[b]\n",
    "\n",
    "        n = len(costs)\n",
    "        s = SortedList(key=functools.cmp_to_key(cmp))\n",
    "        i, j = 0, n - 1\n",
    "        while i <= j and i < candidates:\n",
    "            s.add(i)\n",
    "            if i != j:\n",
    "                s.add(j)\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        ans = 0\n",
    "        while k > 0 and s:\n",
    "            k -= 1\n",
    "            p = s.pop(0)\n",
    "            ans += costs[p]\n",
    "            if i > j:\n",
    "                continue\n",
    "            if p < i:\n",
    "                s.add(i)\n",
    "                i += 1\n",
    "            elif p > j:\n",
    "                s.add(j)\n",
    "                j -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, cn: int, mv=[1, -1]) -> int:\n",
    "        res, hp, ptr = 0, sorted((costs[i], 0) for i in range(cn)), [cn, len(costs) - 1]\n",
    "        while ptr[0] < ptr[1] and len(costs) - ptr[1] <= cn:\n",
    "            heappush(hp, (costs[ptr[1]], 1))\n",
    "            ptr[1] -= 1\n",
    "        for _ in range(k):\n",
    "            c, t = heappop(hp)\n",
    "            res += c\n",
    "            if ptr[0] <= ptr[1]:\n",
    "                heappush(hp, (costs[ptr[t]], t))\n",
    "                ptr[t] += mv[t]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        ans = 0\n",
    "        heap = []\n",
    "        n = len(costs)\n",
    "        L = candidates\n",
    "        R = n - candidates - 1\n",
    "        for i, c in enumerate(costs):\n",
    "            if not L <= i <= R:\n",
    "                if i < L:\n",
    "                    heappush(heap, (c, i, 1))\n",
    "                else:\n",
    "                    heappush(heap, (c, i, 0))\n",
    "        while k:\n",
    "            c, i, left = heappop(heap)\n",
    "            if L <= R:\n",
    "                if left:\n",
    "                    heappush(heap, (costs[L], L, 1))\n",
    "                    L += 1\n",
    "                else:\n",
    "                    heappush(heap, (costs[R], R, 0))\n",
    "                    R -= 1\n",
    "            ans += c\n",
    "            k -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        l = len(costs)\n",
    "        if candidates*2>=l:\n",
    "            return sum(heapq.nsmallest(k,costs))\n",
    "        \n",
    "        left,right = [],[]\n",
    "        for i in range(candidates):\n",
    "            heapq.heappush(left,costs[i])\n",
    "            heapq.heappush(right,costs[-1-i])\n",
    "        \n",
    "        total = 0\n",
    "        index_l,index_r = candidates-1,-candidates\n",
    "        for i in range(k):\n",
    "            if index_l+1==index_r+l:\n",
    "                total+=(sum(heapq.nsmallest(k-i,left+right)))\n",
    "                break\n",
    "            if left[0]<=right[0]:\n",
    "                total+=heapq.heapreplace(left,costs[index_l+1])\n",
    "                index_l+=1\n",
    "            else:\n",
    "                total+=heapq.heapreplace(right,costs[index_r-1])\n",
    "                index_r-=1\n",
    "            \n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        result, i, j = 0, candidates-1, len(costs)-candidates\n",
    "        if i+1 >= j:\n",
    "            return sum(nsmallest(k, costs))\n",
    "        left, right = costs[:candidates], costs[-candidates:]\n",
    "        heapify(left) or heapify(right)\n",
    "        while k and i+1 < j:\n",
    "            if left[0] <= right[0]:\n",
    "                result += heapreplace(left, costs[i := i+1])\n",
    "            else:\n",
    "                result += heapreplace(right, costs[j := j-1])\n",
    "            k -= 1\n",
    "        if k:\n",
    "            result += sum(nsmallest(k, heapq.merge(left, right)))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        result, n, h = 0, len(costs), []\n",
    "        if candidates * 2 >= n:\n",
    "            return sum(nsmallest(k, costs))\n",
    "        left, right = costs[:candidates], costs[-candidates:]\n",
    "        heapify(left) or heapify(right)\n",
    "        i, j = candidates-1, n-candidates\n",
    "        while k and i+1 < j:\n",
    "            if left[0] <= right[0]:\n",
    "                result += heapreplace(left, costs[i := i+1])\n",
    "            else:\n",
    "                result += heapreplace(right, costs[j := j-1])\n",
    "            k -= 1\n",
    "        if k:\n",
    "            result += sum(nsmallest(k, left + right))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        if candidates*2>=len(costs):\n",
    "            heapify(costs)\n",
    "            return sum(heapq.nsmallest(k,costs))\n",
    "        r=len(costs)-1\n",
    "        hp=[]\n",
    "        for i in range(candidates):\n",
    "            hp.append((costs[i],i))\n",
    "            hp.append((costs[r-i],r-i))\n",
    "        heapify(hp)\n",
    "        l=candidates\n",
    "        r-=candidates\n",
    "        res=0\n",
    "        while k:\n",
    "            x,y=hp[0]\n",
    "            if r>=l:\n",
    "                if y<l:\n",
    "                    heapq.heapreplace(hp,(costs[l],l))\n",
    "                    l+=1\n",
    "                if y>r:\n",
    "                    heapq.heapreplace(hp,(costs[r],r))\n",
    "                    r-=1\n",
    "                res+=x\n",
    "            else:\n",
    "                res+=sum(j[0] for j in heapq.nsmallest(k,hp))\n",
    "                break\n",
    "            k-=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        import heapq\n",
    "        cand_cost = []\n",
    "        i = 0\n",
    "        while i < candidates:\n",
    "            lst_i = len(costs) - 1 - i\n",
    "            if i < lst_i:\n",
    "                heapq.heappush(cand_cost, (costs[i], i))\n",
    "                heapq.heappush(cand_cost, (costs[lst_i], lst_i))\n",
    "                i += 1\n",
    "            elif i == lst_i:\n",
    "                heapq.heappush(cand_cost, (costs[i], i))\n",
    "                break\n",
    "            else:\n",
    "                break\n",
    "        res = 0\n",
    "        l = candidates - 1\n",
    "        r = len(costs) - candidates\n",
    "        while k > 0:\n",
    "            popped = heapq.heappop(cand_cost)\n",
    "            res += popped[0]\n",
    "            if popped[1] <= l and l + 1 < r:\n",
    "                heapq.heappush(cand_cost, (costs[l + 1], l + 1))\n",
    "                l += 1\n",
    "            elif popped[1] >= r and r - 1 > l:\n",
    "                heapq.heappush(cand_cost, (costs[r - 1], r - 1))\n",
    "                r -= 1\n",
    "            k -= 1\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        n = len(costs)\n",
    "        costs = deque(costs)\n",
    "        q = []\n",
    "        for i in range(candidates):\n",
    "            if costs:\n",
    "                heapq.heappush(q, (costs.popleft(), 0))\n",
    "        for i in range(candidates):\n",
    "            if costs:\n",
    "                heapq.heappush(q, (costs.pop(), 1))\n",
    "        \n",
    "        ans = 0\n",
    "        for _ in range(k):\n",
    "            cost, d = heappop(q)\n",
    "            ans += cost\n",
    "            if d == 0 and costs:\n",
    "                heapq.heappush(q, (costs.popleft(), 0))\n",
    "            elif d == 1 and costs:\n",
    "                heapq.heappush(q, (costs.pop(), 1))\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        i, j = candidates, max(candidates, len(costs) - candidates)\n",
    "        h1 = list(zip(costs[:candidates], range(candidates)))\n",
    "        h2 = list(zip(costs[j:], range(j, len(costs))))\n",
    "        heapq.heapify(h1)\n",
    "        heapq.heapify(h2)\n",
    "        ans = 0\n",
    "        for _ in range(k):\n",
    "            if len(h2) == 0 or h1 and h1[0][0] <= h2[0][0]:\n",
    "                ans += costs[h1[0][1]]\n",
    "                if i < j:\n",
    "                    heapq.heapreplace(h1, (costs[i], i))\n",
    "                    i += 1\n",
    "                else:\n",
    "                    heapq.heappop(h1)\n",
    "            else:\n",
    "                ans += costs[h2[0][1]]\n",
    "                if i < j:\n",
    "                    heapq.heapreplace(h2, (costs[j - 1], j - 1))\n",
    "                    j -= 1\n",
    "                else:\n",
    "                    heapq.heappop(h2)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        n = len(costs)\n",
    "        if 2 * candidates >= n:\n",
    "            return sum( [ x for x, _ in sorted( [ (x, i) for x, i in zip(costs, range(n)) ] )[:k] ] )\n",
    "        left = [(x, i) for x, i in zip(costs[:candidates], range(candidates))]\n",
    "        i = candidates\n",
    "        j = n - candidates - 1\n",
    "        right = [(x, i) for x, i in zip(costs[-candidates:], range(n - candidates, n, 1))]\n",
    "        heapify(left)\n",
    "        heapify(right)\n",
    "        ans = 0\n",
    "        while k and i <= j:\n",
    "            if left[0][0] <= right[0][0]:\n",
    "                ans += heappop(left)[0]\n",
    "                heappush(left, (costs[i], i))\n",
    "                i += 1\n",
    "            else:\n",
    "                ans += heappop(right)[0]\n",
    "                heappush(right, (costs[j], j))\n",
    "                j -= 1\n",
    "            k -= 1\n",
    "        if k:\n",
    "            h = left + right\n",
    "            heapify(h)\n",
    "            while k:\n",
    "                ans += heappop(h)[0]\n",
    "                k -= 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        n = len(costs)\n",
    "        \n",
    "        i = 0\n",
    "        j = n - 1\n",
    "        if n <= k:\n",
    "            return sum(costs)\n",
    "        hp1 = [(c, i) for i, c in enumerate(costs[:candidates])]\n",
    "        st2 = max(n - candidates, candidates)\n",
    "        hp2 = [(costs[i], i) for i in range(st2, n)]\n",
    "        heapq.heapify(hp1)\n",
    "        heapq.heapify(hp2)\n",
    "        i = candidates - 1\n",
    "        j = st2\n",
    "        ret = 0 \n",
    "        while k > 0:\n",
    "            choose1 = True\n",
    "            if hp1 and hp2:\n",
    "                if hp1[0][0] > hp2[0][0]:\n",
    "                    choose1 = False\n",
    "            elif not hp1:\n",
    "                choose1 = False \n",
    "\n",
    "            if choose1:\n",
    "                #ret.append(heapq.heappop(hp1)[0])\n",
    "                ret += heapq.heappop(hp1)[0]\n",
    "                if i < j - 1:\n",
    "                    i += 1\n",
    "                    heapq.heappush(hp1, (costs[i], i))\n",
    "            else:\n",
    "                #ret.append(heapq.heappop(hp2)[0])  \n",
    "                ret += heapq.heappop(hp2)[0] \n",
    "                if j > i + 1:\n",
    "                    j -= 1\n",
    "                    heapq.heappush(hp2, (costs[j], j)) \n",
    "            k -= 1\n",
    "        return ret\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        size = len(costs)\n",
    "        i,j = candidates-1,size-candidates\n",
    "        res = 0\n",
    "        flag = 0\n",
    "        heap1 = costs[:i+1]\n",
    "        heap2 = costs[j:]\n",
    "        heapify(heap1)\n",
    "        heapify(heap2)\n",
    "        print(costs)\n",
    "        for m in range(k):\n",
    "            if i < j-1:\n",
    "                val = min(heap1[0],heap2[0])\n",
    "                res += val\n",
    "                if val == heap1[0]:\n",
    "                    heappop(heap1)\n",
    "                    i += 1\n",
    "                    heappush(heap1,costs[i])\n",
    "                else:\n",
    "                    heappop(heap2)\n",
    "                    j -= 1\n",
    "                    heappush(heap2,costs[j])\n",
    "            else:\n",
    "                flag = 1\n",
    "                heap3 = heap1+heap2\n",
    "                break\n",
    "        if flag:\n",
    "            heapify(heap3)\n",
    "            nums = heapq.nsmallest(k-m,heap3)\n",
    "            if m == 0:\n",
    "                nums = sorted(costs)[:k]\n",
    "            return res+sum(nums)\n",
    "        else:\n",
    "            return res\n",
    "# class Solution:\n",
    "#     def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "#         ans, n = 0, len(costs)\n",
    "#         if candidates * 2 < n:\n",
    "#             pre = costs[:candidates]\n",
    "#             heapify(pre)\n",
    "#             suf = costs[-candidates:]\n",
    "#             heapify(suf)\n",
    "#             i, j = candidates, n - 1 - candidates\n",
    "#             while k and i <= j:\n",
    "#                 if pre[0] <= suf[0]:\n",
    "#                     ans += heapreplace(pre, costs[i])\n",
    "#                     i += 1\n",
    "#                 else:\n",
    "#                     ans += heapreplace(suf, costs[j])\n",
    "#                     j -= 1\n",
    "#                 k -= 1\n",
    "#             costs = pre + suf\n",
    "#         costs.sort()\n",
    "#         print(costs[:k])\n",
    "#         return ans + sum(costs[:k])  # 也可以用快速选择算法求前 k 小"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, co: List[int], k: int, c: int) -> int:\n",
    "        q = []\n",
    "        t = c\n",
    "        tt = len(co) - c - 1\n",
    "        for i in range(c):\n",
    "            heapq.heappush(q, (co[i], i))\n",
    "            heapq.heappush(q, (co[len(co) - 1 - i], len(co) - 1 - i))\n",
    "            if i >= len(co) - 1 - i:\n",
    "                t = -1\n",
    "                tt = len(co)\n",
    "                break\n",
    "        ans = 0\n",
    "        while k:\n",
    "            while 1:\n",
    "                n = heapq.heappop(q)\n",
    "                if co[n[1]] != -1:\n",
    "                    break\n",
    "            i = n[1]\n",
    "            ans += co[i]\n",
    "            co[i] = -1\n",
    "            if i < t:\n",
    "                heapq.heappush(q, (co[t], t))\n",
    "                t += 1\n",
    "            elif i > tt:\n",
    "                heapq.heappush(q, (co[tt], tt))\n",
    "                tt -= 1\n",
    "            \n",
    "            if t > tt:\n",
    "                t = -1\n",
    "                tt = len(co)\n",
    "            k -= 1\n",
    "        return ans\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        n = len(costs)\n",
    "        if n <= k:\n",
    "            return sum(costs)\n",
    "        if n <= 2 * candidates:\n",
    "            return sum(sorted(costs)[:k])\n",
    "        costs = list((v, i) for i, v in enumerate(costs))\n",
    "        left, right = candidates, n - candidates - 1\n",
    "        q = costs[:left] + costs[right + 1:]\n",
    "        heapq.heapify(q)\n",
    "        ans = 0\n",
    "        while k and left <= right:\n",
    "            v, i = heapq.heappop(q)\n",
    "            ans += v\n",
    "            if i < left:\n",
    "                heapq.heappush(q, costs[left])\n",
    "                left += 1\n",
    "            else:\n",
    "                heapq.heappush(q, costs[right])\n",
    "                right -= 1\n",
    "            k -= 1\n",
    "        ans += sum(v for v, _ in sorted(q)[:k])\n",
    "        return ans\n",
    "\n",
    "        # n = len(costs)\n",
    "        # if n <= k:\n",
    "        #     return sum(costs)\n",
    "        # if n <= 2 * candidates:\n",
    "        #     return sum(sorted(costs)[:k])\n",
    "        # left, right = candidates, n - candidates - 1\n",
    "        # lq, rq = costs[:left], costs[right + 1:]\n",
    "        # heapq.heapify(lq)\n",
    "        # heapq.heapify(rq)\n",
    "        # ans = 0\n",
    "        # import ipdb;ipdb.set_trace()\n",
    "        # while k:\n",
    "        #     if lq[0] <= rq[0]:\n",
    "        #         ans += heapq.heappop(lq)\n",
    "        #         heapq.heappush(lq, costs[left])\n",
    "        #         left += 1\n",
    "        #     else:\n",
    "        #         ans += heapq.heappop(rq)\n",
    "        #         heapq.heappush(rq, costs[right])\n",
    "        #         right -= 1\n",
    "        #     k -= 1\n",
    "        # return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        p = candidates\n",
    "        n = len(costs)\n",
    "        if n < 2*p:\n",
    "            heap = [(v, 0) for v in costs]\n",
    "        else:\n",
    "            heap = [(v, 0) for v in costs[:p]] + [(v, 1) for v in costs[-p:]]\n",
    "        heapify(heap)\n",
    "\n",
    "        i, j = p, n-p-1\n",
    "        res = 0\n",
    "        for _ in range(k):\n",
    "            cost, group = heappop(heap)\n",
    "            res += cost\n",
    "            if i <= j:\n",
    "                if group == 0:\n",
    "                    heappush(heap, (costs[i], 0))\n",
    "                    i += 1\n",
    "                else:\n",
    "                    heappush(heap, (costs[j], 1))\n",
    "                    j -= 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# import heapq\n",
    "# class Solution:\n",
    "#     def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "#         n = len(costs)\n",
    "#         if not costs:\n",
    "#             return 0\n",
    "#         if candidates*2>=n:\n",
    "#             costs=sorted(costs)\n",
    "#             #print(costs)\n",
    "#             return sum(costs[:k])\n",
    "#         else:\n",
    "#             a=candidates\n",
    "#             b=-1*candidates-1\n",
    "#             result=0\n",
    "            \n",
    "#             left=costs[:a]\n",
    "#             heapq.heapify(left)\n",
    "#             right=costs[b+1:]\n",
    "#             heapq.heapify(right)\n",
    "#             print(left)\n",
    "#             print(right)\n",
    "#             while k>0:\n",
    "#                 if left[0]<=right[0]:\n",
    "#                     result+=heapq.heappop(left)\n",
    "#                     heapq.heappush(left, costs[a])\n",
    "#                     a+=1\n",
    "#                 else:\n",
    "#                     result+=heapq.heappop(right)\n",
    "#                     heapq.heappush(right, costs[b])\n",
    "#                     b-=1\n",
    "#                 k-=1\n",
    "#                 print(result,a,b)\n",
    "#                 print(left)\n",
    "#                 print(right)\n",
    "\n",
    "#             return result\n",
    "class Solution(object):\n",
    "    def totalCost(self, costs, k, candidates):\n",
    "        \"\"\"\n",
    "        :type costs: List[int]\n",
    "        :type k: int\n",
    "        :type candidates: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        n = len(costs)\n",
    "        heap = []\n",
    "        res = 0\n",
    "\n",
    "        if candidates * 2 < n:\n",
    "            left = candidates - 1\n",
    "            right = n - candidates\n",
    "            for index in range(left + 1):\n",
    "                heapq.heappush(heap, [costs[index], index])\n",
    "            for index in range(right, n):\n",
    "                heapq.heappush(heap, [costs[index], index])\n",
    "\n",
    "            while left + 1 < right and k > 0:\n",
    "                min_cost, index = heapq.heappop(heap)\n",
    "                res += min_cost\n",
    "                if index <= left:\n",
    "                    left += 1\n",
    "                    heapq.heappush(heap, [costs[left], left])\n",
    "                else:\n",
    "                    right -= 1\n",
    "                    heapq.heappush(heap, [costs[right], right])\n",
    "\n",
    "                k -= 1\n",
    "\n",
    "        else:\n",
    "            for index in range(n):\n",
    "                heapq.heappush(heap, [costs[index], index])\n",
    "\n",
    "        while k > 0:\n",
    "            min_cost, index = heapq.heappop(heap)\n",
    "            res += min_cost\n",
    "            k -= 1\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def compare(t1, t2):\n",
    "    if t1[0] < t2[0]:\n",
    "        return True\n",
    "    elif t1[0] == t2[0]:\n",
    "        if t1[1] < t2[1]:\n",
    "            return True\n",
    "    return False\n",
    "\n",
    "class Array:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.a = []\n",
    "        self.n = 0\n",
    "\n",
    "    def sink(self, b, e):\n",
    "        p, i = b, b * 2 + 1\n",
    "        x = self.a[p]\n",
    "        while i < e:\n",
    "            if i + 1 < e and compare(self.a[i + 1], self.a[i]):\n",
    "                i += 1\n",
    "            if compare(x, self.a[i]):\n",
    "                break\n",
    "            self.a[p] = self.a[i]\n",
    "            p, i = i, i * 2 + 1\n",
    "        self.a[p] = x\n",
    "\n",
    "    def adjust(self):\n",
    "        p, i = (self.n - 2) // 2, self.n - 1\n",
    "        x = self.a[i]\n",
    "        while p >= 0:\n",
    "            if compare(self.a[p], x):\n",
    "                break\n",
    "            self.a[i] = self.a[p]\n",
    "            p, i = (p - 1) // 2, p\n",
    "        self.a[i] = x\n",
    "\n",
    "    def insert(self, k):\n",
    "        self.a.append(k)\n",
    "        self.n += 1\n",
    "        self.adjust()\n",
    "\n",
    "    def pop(self):\n",
    "        if self.n == 0:\n",
    "            return -1\n",
    "        x, self.a[0] = self.a[0], self.a[self.n - 1]\n",
    "        self.n -= 1\n",
    "        self.a.pop()\n",
    "        if self.n:\n",
    "            self.sink(0, self.n)\n",
    "        return x\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        n = len(costs)\n",
    "        l, r = candidates - 1, n - candidates\n",
    "        heap = Array()\n",
    "        for i in range(l + 1):\n",
    "            heap.insert([costs[i], i])\n",
    "        for i in range(l + 1 if l >= r else r, n):\n",
    "            heap.insert([costs[i], i])\n",
    "        ans = 0\n",
    "        for j in range(k):\n",
    "            minc, i = heap.pop()\n",
    "            ans += minc\n",
    "            if l < r - 1:\n",
    "                if i <= l:\n",
    "                    l += 1\n",
    "                    heap.insert([costs[l], l])\n",
    "                else:\n",
    "                    r -= 1\n",
    "                    heap.insert([costs[r], r])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        res = 0\n",
    "        n = len(costs)\n",
    "        q = queue.PriorityQueue()\n",
    "        l = candidates - 1\n",
    "        r = n - candidates\n",
    "        for i in range(l+1):\n",
    "            q.put([costs[i], i])\n",
    "        if r - l >= 1:\n",
    "            for i in range(n-1, r - 1, -1):\n",
    "                q.put([costs[i], i])\n",
    "        else:\n",
    "            for i in range(l+1, n):\n",
    "                q.put([costs[i], i])\n",
    "\n",
    "        for i in range(k):\n",
    "            [cost, idx] = q.get()   \n",
    "            res += cost\n",
    "            if r - l >= 2:\n",
    "                if idx <= l:\n",
    "                    l += 1\n",
    "                    q.put([costs[l], l])\n",
    "                else:\n",
    "                    r -= 1\n",
    "                    q.put([costs[r], r])\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, c: int) -> int:\n",
    "        import heapq as heap\n",
    "        costs = [(cost,idx) for idx,cost in enumerate(costs)]\n",
    "        # print(costs)\n",
    "        n = len(costs)\n",
    "        start = 0\n",
    "        end = n - 1\n",
    "        head = []\n",
    "        tail = []\n",
    "        res = 0\n",
    "        used = set()\n",
    "        def compare(a,b):\n",
    "            if not a:\n",
    "                return False\n",
    "            if not b:\n",
    "                return True\n",
    "            if a[0] < b[0]:\n",
    "                return True\n",
    "            elif a[0] > b[0]:\n",
    "                return False\n",
    "            else:\n",
    "                if a[1] < b[1]:\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "\n",
    "        while k:\n",
    "            while len(head) < c and start < end:\n",
    "                heap.heappush(head,costs[start])\n",
    "                start += 1\n",
    "            while len(tail) < c and start <= end:\n",
    "                heap.heappush(tail,costs[end])\n",
    "                end -= 1\n",
    "            # print(head,tail,111)\n",
    "            a = heap.heappop(head) if len(head) != 0 else None\n",
    "            b = heap.heappop(tail) if len(tail) != 0 else None\n",
    "            temp = 0 \n",
    "            if compare(a,b):\n",
    "                if b:\n",
    "                    heap.heappush(tail,b) \n",
    "                if a:\n",
    "                    res += a[0]\n",
    "                    temp = a[0]\n",
    "            else:\n",
    "                if a:\n",
    "                    heap.heappush(head,a)\n",
    "                if b:\n",
    "                    res += b[0]\n",
    "                    temp = b[0]\n",
    "            # print(a,b,res,temp)\n",
    "            k -= 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        n = len(costs)\n",
    "        dq = deque()\n",
    "        for i in range(n):\n",
    "            dq.append((costs[i], i))\n",
    "        \n",
    "        res = 0\n",
    "        h = []\n",
    "        for _ in range(candidates):\n",
    "            if dq:\n",
    "                a = dq.popleft()\n",
    "                heapq.heappush(h, a)\n",
    "            if dq:\n",
    "                b = dq.pop()\n",
    "                heapq.heappush(h, b)\n",
    "\n",
    "        while k:\n",
    "            c, i = heapq.heappop(h)\n",
    "            res += c\n",
    "            if dq:\n",
    "                if dq[0][1] >= i:\n",
    "                    a = dq.popleft()\n",
    "                    heapq.heappush(h, a)\n",
    "                else:\n",
    "                    a = dq.pop()\n",
    "                    heapq.heappush(h, a)\n",
    "\n",
    "            k -= 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        n = len(costs)\n",
    "\n",
    "        hp = []\n",
    "        l, r = 0, n-1\n",
    "        for _ in range(candidates):\n",
    "            if l<r:\n",
    "                heappush(hp, (costs[l], False))\n",
    "                heappush(hp, (costs[r], True))\n",
    "            elif l==r:\n",
    "                heappush(hp, (costs[l], False))\n",
    "            l+=1\n",
    "            r-=1\n",
    "        \n",
    "        res = 0\n",
    "        for _ in range(k):\n",
    "            cost, isRight = heappop(hp)\n",
    "            res += cost\n",
    "            if l>r:\n",
    "                continue\n",
    "\n",
    "            if isRight:\n",
    "                heappush(hp, (costs[r], True))\n",
    "                r-=1\n",
    "            else:\n",
    "                heappush(hp, (costs[l], False))\n",
    "                l+=1\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "    lc = len(costs)\n",
    "    if k == lc:\n",
    "      return sum(costs)\n",
    "    q, lp, rp, c = [], 0, lc - 1, 0\n",
    "    while c < 2 * candidates and c < lc:\n",
    "      heapq.heappush(q, (costs[lp], 0))\n",
    "      lp += 1\n",
    "      c += 1\n",
    "      if c < lc:\n",
    "        heapq.heappush(q, (costs[rp], 1))\n",
    "        rp -= 1\n",
    "        c += 1\n",
    "      \n",
    "    ret = 0\n",
    "    for i in range(k):\n",
    "      v, d = heapq.heappop(q)\n",
    "      ret += v\n",
    "      if c < lc:\n",
    "        if 0 == d:\n",
    "          heapq.heappush(q, (costs[lp], 0))\n",
    "          lp += 1\n",
    "          c += 1\n",
    "        else:\n",
    "          heapq.heappush(q, (costs[rp], 1))\n",
    "          rp -= 1\n",
    "          c += 1\n",
    "    # print(f\"lp {lp} {rp}\")\n",
    "    return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        left = candidates - 1\n",
    "        right = len(costs) - candidates\n",
    "        heap = []\n",
    "        for i in range(candidates):\n",
    "            heapq.heappush(heap, (costs[i], 0))\n",
    "            j = right + i\n",
    "            if j >= candidates:\n",
    "                heapq.heappush(heap, (costs[j], 1))\n",
    "        ans = 0\n",
    "        for i in range(k):\n",
    "            cost, index = heapq.heappop(heap)\n",
    "            if index == 0:\n",
    "                left += 1\n",
    "                if left < right:\n",
    "                    heapq.heappush(heap, (costs[left], 0))\n",
    "            else:\n",
    "                right -= 1\n",
    "                if left < right:\n",
    "                    heapq.heappush(heap, (costs[right], 1))\n",
    "            ans += cost\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        candidate_list = []\n",
    "        n = len(costs)\n",
    "        res = 0\n",
    "        for i in range(candidates):\n",
    "            heapq.heappush(candidate_list, (costs[i], 1))\n",
    "        for i in range(n-1, n-1-candidates, -1):\n",
    "            if i > candidates - 1:\n",
    "                heapq.heappush(candidate_list, (costs[i], 2))\n",
    "        \n",
    "        left, right = candidates - 1, n - candidates\n",
    "        print(candidate_list, left, right, n)\n",
    "        for i in range(k):\n",
    "            num, dire = heapq.heappop(candidate_list)\n",
    "            res += num\n",
    "            if right - left > 1:\n",
    "                if dire == 1:\n",
    "                    left += 1\n",
    "                    heapq.heappush(candidate_list, (costs[left], dire))\n",
    "                else:\n",
    "                    right -= 1\n",
    "                    heapq.heappush(candidate_list, (costs[right], dire))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        n = len(costs)\n",
    "\n",
    "        hp = []\n",
    "        l, r = 0, n-1\n",
    "        for _ in range(candidates):\n",
    "            if l<r:\n",
    "                heappush(hp, (costs[l], False))\n",
    "                heappush(hp, (costs[r], True))\n",
    "            elif l==r:\n",
    "                heappush(hp, (costs[l], False))\n",
    "            l+=1\n",
    "            r-=1\n",
    "        \n",
    "        res = 0\n",
    "        for _ in range(k):\n",
    "            cost, isRight = heappop(hp)\n",
    "            res += cost\n",
    "            if l>r:\n",
    "                continue\n",
    "\n",
    "            if isRight:\n",
    "                heappush(hp, (costs[r], True))\n",
    "                r-=1\n",
    "            else:\n",
    "                heappush(hp, (costs[l], False))\n",
    "                l+=1\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList \n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int: \n",
    "        s  = SortedList( )\n",
    "        if ( ( candidates*2) <= len( costs ) ) :  \n",
    "            for j in range( candidates  ) :\n",
    "                s.add( ( costs[j] , j  ) ) \n",
    "            for j in range( len( costs ))[-candidates: ]:\n",
    "                s.add( ( costs[j] , j  ) ) \n",
    "\n",
    "            l=candidates-1 \n",
    "            r = len( costs) - candidates \n",
    "        else:\n",
    "            for j in range( len( costs )):\n",
    "                s.add( ( costs[j] , j ))\n",
    "            l = 0\n",
    "            r = -5\n",
    " \n",
    "        ans = 0 \n",
    "        while k>0 :\n",
    "            tmp =s.pop( 0 ) \n",
    "            ans+= tmp[0 ]\n",
    "            if (l+1)< r:\n",
    "                if tmp[1]<= l :\n",
    "                    l+=1 \n",
    "                    s.add( ( costs[l], l  )) \n",
    "                else:\n",
    "                    r -= 1 \n",
    "                    s.add( ( costs[r], r  )) \n",
    "            k-=1 \n",
    "        return ans \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        l, r = 0, 0\n",
    "        n = len(costs)\n",
    "        from sortedcontainers import SortedList\n",
    "        sl = SortedList()\n",
    "        pos = SortedList()\n",
    "        mask = [0] * n\n",
    "\n",
    "        for p in range(candidates):\n",
    "            if mask[p]: continue\n",
    "            mask[p] = 1\n",
    "            pos.add(p)\n",
    "            sl.add((costs[p], p))\n",
    "            l = p\n",
    "\n",
    "        for p in range(candidates):\n",
    "            p2 = n - 1 - p\n",
    "            if mask[p2]: continue\n",
    "            mask[p2] = 1\n",
    "            pos.add(p2)\n",
    "            sl.add((costs[p2], p2))\n",
    "            r = p2\n",
    "\n",
    "        # print(costs)\n",
    "        # print(sl, pos)\n",
    "        ans = 0\n",
    "        for round in range(k):\n",
    "            (c, p) = sl.pop(0)\n",
    "            # print('select ', c, p)\n",
    "            ans += c\n",
    "            i = pos.index(p)\n",
    "            pos.remove(p)\n",
    "\n",
    "            if i < candidates:\n",
    "                while l < r and mask[l]: l += 1\n",
    "                p = l\n",
    "            else:\n",
    "                while l < r and mask[r]: r -= 1\n",
    "                p = r\n",
    "\n",
    "            if mask[p]: continue\n",
    "            sl.add((costs[p], p))\n",
    "            pos.add(p)\n",
    "            mask[p] = 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        import heapq\n",
    "        heap = []\n",
    "        n = len(costs)\n",
    "        for i in range(min(n, candidates)):\n",
    "            heapq.heappush(heap, (costs[i],i))\n",
    "        \n",
    "        i = min(n, candidates) - 1\n",
    "        \n",
    "        for j in range(n-1,max(i, n-candidates-1),-1):\n",
    "            heapq.heappush(heap, (costs[j],j))\n",
    "        \n",
    "        j = max(i, n-candidates-1) + 1\n",
    "        \n",
    "        cost = 0\n",
    "        for r in range(k):\n",
    "            c, idx = heapq.heappop(heap)\n",
    "            cost += c\n",
    "            if idx <= i and i+1 < j:\n",
    "                i += 1\n",
    "                heapq.heappush(heap, (costs[i], i))\n",
    "            elif idx >= j and j-1 > i:\n",
    "                j -= 1\n",
    "                heapq.heappush(heap, (costs[j], j))\n",
    "        \n",
    "        return cost\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        #copy\n",
    "        n= len(costs)\n",
    "        pq = []\n",
    "        for left in range(candidates):\n",
    "            heapq.heappush(pq,(costs[left],left))\n",
    "\n",
    "        right = n-1\n",
    "        for right in range(n-1,max(left,n-candidates-1),-1):\n",
    "            heapq.heappush(pq,(costs[right],right))\n",
    "\n",
    "        ans = 0\n",
    "        while k:\n",
    "            cost,i = heapq.heappop(pq)\n",
    "            ans += cost\n",
    "            if i <= left:\n",
    "                left += 1\n",
    "                if left<right:\n",
    "                    heapq.heappush(pq,(costs[left],left))\n",
    "            \n",
    "            elif i >= right:\n",
    "                right -=1\n",
    "                if left<right:\n",
    "                    heapq.heappush(pq,(costs[right],right))\n",
    "            \n",
    "            k-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        n = len(costs)\n",
    "        h = []\n",
    "        left, right = -1, n\n",
    "        for i in range(candidates):\n",
    "            left += 1\n",
    "            heappush(h, (costs[left], left))\n",
    "        \n",
    "        for i in range(candidates):\n",
    "            if right - left > 1:\n",
    "                right -= 1\n",
    "                heappush(h, (costs[right], right))\n",
    "        total = 0\n",
    "        for i in range(k):\n",
    "            cost, idx = heappop(h)\n",
    "            total += cost\n",
    "            if right - left > 1:\n",
    "                if idx <= left:\n",
    "                    left += 1\n",
    "                    heappush(h, (costs[left], left))\n",
    "                else:\n",
    "                    right -= 1\n",
    "                    heappush(h, (costs[right], right))\n",
    "        return total\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        if not k:\n",
    "            return 0\n",
    "\n",
    "        q = []\n",
    "        l, r = candidates - 1, len(costs) - candidates\n",
    "        for i in range(l + 1):\n",
    "            heappush(q, (costs[i], i))\n",
    "        for i in range(max(l + 1, r), len(costs)):\n",
    "            heappush(q, (costs[i], i))\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(k):\n",
    "            x = heappop(q)\n",
    "            ans += x[0]\n",
    "            if r - l > 1:\n",
    "                if x[1] <= l:\n",
    "                    l += 1\n",
    "                    heappush(q, (costs[l], l))\n",
    "                elif x[1] >= r:\n",
    "                    r -= 1\n",
    "                    heappush(q, (costs[r], r))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        import heapq\n",
    "        from collections import deque\n",
    "\n",
    "        n = len(costs)\n",
    "        if candidates * 2 >= n:\n",
    "            queue = deque()\n",
    "            heap = [(x, i) for i, x in enumerate(costs)]\n",
    "        else:\n",
    "            queue = deque(costs[candidates:-candidates])\n",
    "            heap = [(x, 0) for i, x in enumerate(costs) if i < candidates] + \\\n",
    "                [(x, 1) for i, x in enumerate(costs) if i >= n - candidates]\n",
    "        heapq.heapify(heap)\n",
    "        \n",
    "        res = 0\n",
    "        for _ in range(k):\n",
    "            x, i = heapq.heappop(heap)\n",
    "            res += x\n",
    "            if i == 0 and queue:\n",
    "                heapq.heappush(heap, (queue.popleft(), 0))\n",
    "            elif i == 1 and queue:\n",
    "                heapq.heappush(heap, (queue.pop(), 1))\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        costs_new = []\n",
    "        result = 0\n",
    "        for i, x in enumerate(costs):\n",
    "            costs_new.append([x, i])\n",
    "        k1 = 0\n",
    "        k2 = 0\n",
    "        if len(costs_new) > 2 * candidates:\n",
    "            heap1 = costs_new[0:candidates] + costs_new[-candidates:]\n",
    "            heapq.heapify(heap1)\n",
    "            k1 = candidates - 1\n",
    "            k2 = len(costs_new) - candidates\n",
    "        else:\n",
    "            heap1 = costs_new\n",
    "            heapq.heapify(heap1)\n",
    "\n",
    "        for i in range(k):\n",
    "            min_x = heapq.heappop(heap1)\n",
    "            result = result + min_x[0]\n",
    "            if k1 +1 < k2:\n",
    "                if min_x[1] <= k1:\n",
    "                    k1 = k1 + 1\n",
    "                    heapq.heappush(heap1,costs_new[k1])\n",
    "                if min_x[1] >= k2:\n",
    "                    k2 = k2 - 1\n",
    "                    heapq.heappush(heap1,costs_new[k2])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        l,r = 0,len(costs)-1\n",
    "        res = 0\n",
    "        leftcost,rightcost = [], []\n",
    "        count = 0\n",
    "        while l<=r and l<candidates:\n",
    "            heapq.heappush(leftcost, (costs[l],l))\n",
    "            l+=1\n",
    "        while l<=r and len(costs)-1-r<candidates:\n",
    "            heapq.heappush(rightcost, (costs[r],r))\n",
    "            r-=1\n",
    "\n",
    "        for i in range(k):\n",
    "            if not leftcost and not rightcost:\n",
    "                return res\n",
    "            elif not leftcost:\n",
    "                res+=heapq.heappop(rightcost)[0]\n",
    "                if l<=r:\n",
    "                    heapq.heappush(rightcost, (costs[r],r))\n",
    "                    r-=1\n",
    "            elif not rightcost or leftcost[0]<=rightcost[0]:\n",
    "                res+=heapq.heappop(leftcost)[0]\n",
    "                if l<=r:\n",
    "                    heapq.heappush(leftcost, (costs[l],l))\n",
    "                    l+=1\n",
    "            else:\n",
    "                res+=heapq.heappop(rightcost)[0]\n",
    "                if l<=r:\n",
    "                    heapq.heappush(rightcost, (costs[r],r))\n",
    "                    r-=1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        res = 0\n",
    "        left, right = candidates - 1, len(costs) - candidates\n",
    "        initcosts = (costs[:left+1] + costs[right:]) if len(costs) > 2*candidates else costs\n",
    "        pq = [(costs[i], i) for i in range(left+1)] + [(costs[i], i) for i in range(right, len(costs))] if len(costs) > 2*candidates else [(costs[i], i) for i in range(len(costs))]\n",
    "        heapq.heapify(pq)\n",
    "\n",
    "        for _ in range(k):\n",
    "            cost, i = heapq.heappop(pq)\n",
    "            if i <= left and left + 1 < right:\n",
    "                left += 1\n",
    "                heapq.heappush(pq, (costs[left], left))\n",
    "            elif i >= right and right - 1 > left:\n",
    "                right -=1\n",
    "                heapq.heappush(pq, (costs[right], right))\n",
    "            res += cost\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:      \n",
    "        left = candidates - 1\n",
    "        n = len(costs)\n",
    "        right = n - candidates if 2*candidates < n else left + 1\n",
    "\n",
    "        ans = 0\n",
    "        heap = []\n",
    "        for index,v in enumerate(costs[:left+1]):\n",
    "            heappush(heap,(v,index))\n",
    "        for index,v in enumerate(costs[right:]):\n",
    "            heappush(heap,(v,index + right))\n",
    "        \n",
    "        while k > 0:   \n",
    "            v, index = heappop(heap)\n",
    "            ans += v\n",
    "            if index <= left:\n",
    "                left += 1\n",
    "                if left < right:\n",
    "                    heappush(heap,(costs[left],left))   \n",
    "            else:\n",
    "                right -= 1\n",
    "                if left < right:\n",
    "                    heappush(heap,(costs[right],right))     \n",
    "            k -= 1                \n",
    "        \n",
    "        return ans   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        ans=0\n",
    "        n=len(costs)\n",
    "        temp=max(candidates, n-candidates)\n",
    "        arr=[(costs[i],i,'f') for i in range(candidates)]+[(costs[i],i,'b') for i in range(temp,n)]\n",
    "        heapq.heapify(arr)\n",
    "        left=candidates\n",
    "        right=temp-1\n",
    "        cnt=0\n",
    "        while cnt<k:\n",
    "            cost,_,direct=heapq.heappop(arr)\n",
    "            ans+=cost\n",
    "            cnt+=1\n",
    "            if left<=right:\n",
    "                if direct=='f':\n",
    "                    heapq.heappush(arr,(costs[left],left,'f'))\n",
    "                    left+=1\n",
    "                else:\n",
    "                    heapq.heappush(arr,(costs[right],right,'b'))\n",
    "                    right-=1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        start, end = 0, len(costs)-1\n",
    "        cost = 0\n",
    "        h1, h2 = [], []\n",
    "        while len(h1) < candidates and start <= end:\n",
    "            heapq.heappush(h1, (costs[start], start))\n",
    "            start += 1\n",
    "        while len(h2) < candidates and start <= end:\n",
    "            heapq.heappush(h2, (costs[end], end))\n",
    "            end -= 1\n",
    "\n",
    "        while k > 0:\n",
    "            if len(h1) > 0 and (len(h2) == 0 or h1[0] < h2[0]):\n",
    "                c1, i1 = heapq.heappop(h1)\n",
    "                # print('hire', c1, i1)\n",
    "                cost += c1\n",
    "                if start <= end:\n",
    "                    heapq.heappush(h1, (costs[start], start))\n",
    "                    start += 1\n",
    "            else:\n",
    "                c2, i2 = heapq.heappop(h2)\n",
    "                # print('hire', c2, i2)\n",
    "                cost += c2\n",
    "                if start <= end:\n",
    "                    heapq.heappush(h2, (costs[end], end))\n",
    "                    end -= 1\n",
    "            k -= 1\n",
    "\n",
    "        return cost\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        n = len(costs)\n",
    "        q = []\n",
    "        if candidates *2 >= n:\n",
    "            for i in range(n):\n",
    "                q.append((costs[i], i))\n",
    "            left, right = n, -1\n",
    "        else:\n",
    "            for i in range(candidates):\n",
    "                q.append((costs[i], i))\n",
    "                q.append((costs[n-1-i], n-1-i))\n",
    "            left, right = candidates, n-1-candidates\n",
    "        heapq.heapify(q)\n",
    "        ans = 0\n",
    "        while k:\n",
    "            k -= 1\n",
    "            min_val, min_idx = heapq.heappop(q)\n",
    "            ans += min_val\n",
    "            if left > right:\n",
    "                continue\n",
    "            if min_idx < left and left < n:\n",
    "                heapq.heappush(q, (costs[left], left))\n",
    "                left += 1\n",
    "            elif min_idx > right and right >= 0:\n",
    "                heapq.heappush(q, (costs[right], right))\n",
    "                right -= 1\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        from queue import PriorityQueue\n",
    "\n",
    "        queue = PriorityQueue()\n",
    "        for i in range(candidates):\n",
    "            queue.put((costs[i], i))\n",
    "        for i in range(max(len(costs) - candidates, candidates), len(costs)):\n",
    "            queue.put((costs[i], i))\n",
    "\n",
    "        l = candidates\n",
    "        r = len(costs) - candidates - 1\n",
    "        ret = 0 \n",
    "        for _ in range(k):\n",
    "            cost, idx = queue.get()\n",
    "            #print(cost, idx)\n",
    "            ret += cost\n",
    "            if l <= r:\n",
    "                if idx < l:\n",
    "                    queue.put((costs[l], l))\n",
    "                    l += 1\n",
    "                else:\n",
    "                    queue.put((costs[r], r))\n",
    "                    r -= 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        n = len(costs)\n",
    "        added = [False] * n\n",
    "        heap = []\n",
    "        ans = 0\n",
    "        for i in range(candidates):\n",
    "            if not added[i]:\n",
    "                heapq.heappush(heap, (costs[i], i, 1))\n",
    "                added[i] = True\n",
    "            if not added[n - i - 1]:\n",
    "                heapq.heappush(heap, (costs[n - i - 1], n - i - 1, -1))\n",
    "                added[n - i - 1] = True\n",
    "        left, right = candidates, n - candidates - 1\n",
    "        for i in range(k):\n",
    "            cost, idx, dir = heapq.heappop(heap)\n",
    "            ans += cost\n",
    "            if dir == 1:\n",
    "                if left < n and not added[left]:\n",
    "                    heapq.heappush(heap, (costs[left], left, 1))\n",
    "                    added[left] = True\n",
    "                    left += 1\n",
    "            else:\n",
    "                if right > 0 and not added[right]:\n",
    "                    heapq.heappush(heap, (costs[right], right, -1))\n",
    "                    added[right] = True\n",
    "                    right -= 1\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        n = len(costs)\n",
    "        added = [False] * n\n",
    "        heap = []\n",
    "        ans = 0\n",
    "        for i in range(candidates):\n",
    "            if not added[i]:\n",
    "                heapq.heappush(heap, (costs[i], i, 1))\n",
    "                added[i] = True\n",
    "            if not added[n - i - 1]:\n",
    "                heapq.heappush(heap, (costs[n - i - 1], n - i - 1, -1))\n",
    "                added[n - i - 1] = True\n",
    "        left, right = candidates, n - candidates - 1\n",
    "        for i in range(k):\n",
    "            cost, idx, dir = heapq.heappop(heap)\n",
    "            ans += cost\n",
    "            if dir == 1:\n",
    "                if left < n and not added[left]:\n",
    "                    heapq.heappush(heap, (costs[left], left, 1))\n",
    "                    added[left] = True\n",
    "                    left += 1\n",
    "            else:\n",
    "                if right > 0 and not added[right]:\n",
    "                    heapq.heappush(heap, (costs[right], right, -1))\n",
    "                    added[right] = True\n",
    "                    right -= 1\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        l = []\n",
    "        left = 0\n",
    "        right = len(costs) - 1\n",
    "        for i in range(candidates):\n",
    "            if left <= right:\n",
    "                l.append([costs[left], left])\n",
    "                left += 1\n",
    "                if left <= right:\n",
    "                    l.append([costs[right], right])\n",
    "                    right -= 1\n",
    "        heapq.heapify(l)\n",
    "        sum1 = 0\n",
    "        for i in range(k):\n",
    "            sum1 += l[0][0]\n",
    "            y = l[0][1]\n",
    "            heapq.heappop(l)\n",
    "            if left <= right:\n",
    "                if y < left:\n",
    "                    heapq.heappush(l, [costs[left], left])\n",
    "                    left += 1\n",
    "                elif y > right:\n",
    "                    heapq.heappush(l, [costs[right], right])\n",
    "                    right -= 1\n",
    "        return sum1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        l = []\n",
    "        left = 0\n",
    "        right = len(costs) - 1\n",
    "        for i in range(candidates):\n",
    "            if left <= right:\n",
    "                l.append([costs[left], left])\n",
    "                left += 1\n",
    "                if left <= right:\n",
    "                    l.append([costs[right], right])\n",
    "                    right -= 1\n",
    "        heapq.heapify(l)\n",
    "        sum1 = 0\n",
    "        for i in range(k):\n",
    "            sum1 += l[0][0]\n",
    "            y = l[0][1]\n",
    "            if left <= right:\n",
    "                if y < left:\n",
    "                    heapq.heapreplace(l, [costs[left], left])\n",
    "                    left += 1\n",
    "                elif y > right:\n",
    "                    heapq.heapreplace(l, [costs[right], right])\n",
    "                    right -= 1\n",
    "            else:\n",
    "                heapq.heappop(l)\n",
    "        return sum1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "\n",
    "        all_cost = 0\n",
    "        first_stop = candidates\n",
    "        second_start = len(costs)-candidates\n",
    "\n",
    "        cost_list = [(costs[i], i) for i in range(len(costs))]\n",
    "        candidates_list = cost_list if second_start<= first_stop else cost_list[:first_stop]+cost_list[second_start:]\n",
    "        heapq.heapify(candidates_list)\n",
    "\n",
    "        for i in range(k):\n",
    "            cur_choosen = heapq.heappop(candidates_list)\n",
    "            all_cost += cur_choosen[0]\n",
    "            \n",
    "            if second_start<= first_stop:\n",
    "                continue\n",
    "            \n",
    "\n",
    "            if cur_choosen[1]<first_stop:\n",
    "                heapq.heappush(candidates_list, cost_list[first_stop])\n",
    "                first_stop += 1\n",
    "\n",
    "            elif cur_choosen[1]>=second_start:\n",
    "                second_start -= 1\n",
    "                heapq.heappush(candidates_list, cost_list[second_start])\n",
    "            # print(first_stop, second_start)\n",
    "            # print(\"``````````````````````````````\")\n",
    "        return all_cost\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        n = len(costs)\n",
    "        added = [False] * n\n",
    "        heap = []\n",
    "        ans = 0\n",
    "        for i in range(candidates):\n",
    "            if not added[i]:\n",
    "                heapq.heappush(heap, (costs[i], i, 1))\n",
    "                added[i] = True\n",
    "            if not added[n - i - 1]:\n",
    "                heapq.heappush(heap, (costs[n - i - 1], n - i - 1, -1))\n",
    "                added[n - i - 1] = True\n",
    "        left, right = candidates, n - candidates - 1\n",
    "        for i in range(k):\n",
    "            cost, idx, dir = heapq.heappop(heap)\n",
    "            ans += cost\n",
    "            if dir == 1:\n",
    "                if left < n and not added[left]:\n",
    "                    heapq.heappush(heap, (costs[left], left, 1))\n",
    "                    added[left] = True\n",
    "                    left += 1\n",
    "            else:\n",
    "                if right > 0 and not added[right]:\n",
    "                    heapq.heappush(heap, (costs[right], right, -1))\n",
    "                    added[right] = True\n",
    "                    right -= 1\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:\n",
    "        new_cost = [(num, index) for index, num in enumerate(costs)]\n",
    "\n",
    "        heap = []\n",
    "        length = len(costs)\n",
    "\n",
    "        left = candidates - 1\n",
    "        right = length - candidates\n",
    "        if left < right:\n",
    "            heap = new_cost[:candidates] + new_cost[right :]\n",
    "        else:\n",
    "            heap = new_cost\n",
    "        # print(heap)\n",
    "        heapq.heapify(heap)\n",
    "        cost = 0\n",
    "        for i in range(k):\n",
    "\n",
    "            cur = heapq.heappop(heap)\n",
    "            cost += cur[0]\n",
    "\n",
    "            # it is from left, add from left\n",
    "            if cur[1] <= left:\n",
    "            # print(\"add from left\")\n",
    "                left += 1\n",
    "                if left < right:\n",
    "                    heapq.heappush(heap, new_cost[left] )\n",
    "            \n",
    "            elif cur[1] >= right:\n",
    "            #print(\"add from right\")\n",
    "                right -= 1\n",
    "                if right > left:\n",
    "                    heapq.heappush(heap, new_cost[right] )\n",
    "            \n",
    "    \n",
    "\n",
    "        return cost"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
